//给你一个 m x n 大小的矩阵 grid ，由若干正整数组成。 
//
// 执行下述操作，直到 grid 变为空矩阵： 
//
// 
// 从每一行删除值最大的元素。如果存在多个这样的值，删除其中任何一个。 
// 将删除元素中的最大值与答案相加。 
// 
//
// 注意 每执行一次操作，矩阵中列的数据就会减 1 。 
//
// 返回执行上述操作后的答案。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：grid = [[1,2,4],[3,3,1]]
//输出：8
//解释：上图展示在每一步中需要移除的值。
//- 在第一步操作中，从第一行删除 4 ，从第二行删除 3（注意，有两个单元格中的值为 3 ，我们可以删除任一）。在答案上加 4 。
//- 在第二步操作中，从第一行删除 2 ，从第二行删除 3 。在答案上加 3 。
//- 在第三步操作中，从第一行删除 1 ，从第二行删除 1 。在答案上加 1 。
//最终，答案 = 4 + 3 + 1 = 8 。
// 
//
// 示例 2： 
//
// 
//
// 
//输入：grid = [[10]]
//输出：10
//解释：上图展示在每一步中需要移除的值。
//- 在第一步操作中，从第一行删除 10 。在答案上加 10 。
//最终，答案 = 10 。
// 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n == grid[i].length 
// 1 <= m, n <= 50 
// 1 <= grid[i][j] <= 100 
// 
// Related Topics 数组 矩阵 排序 👍 17 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution2500 {

    /**
     * 冒泡排序取最大值
     * 执行耗时:12 ms,击败了5.08% 的Java用户
     * 内存消耗:41.9 MB,击败了61.69% 的Java用户
     *
     * @param grid
     * @return
     */
    public int deleteGreatestValue(int[][] grid) {
        if(grid[0].length == 1) {
            return grid[0][0];
        }

        // 获取二维数组长度
        int gridLen = grid.length;

        // 获取遍历长度
        int len = grid[0].length;

        // 数组从大到小排序
        for (int[] arr : grid) {
            sort(arr);
        }

        int res = 0;

        // 遍历获取最大值
        for (int i = 0; i < len; i++) {
            int[] tempArr = new int[gridLen];
            for (int k = 0; k < grid.length; k++) {
                tempArr[k] = grid[k][i];
            }

            // 单次冒泡排序返回最大值
            res += oneSortAndReturnMax(tempArr);
        }
        return res;
    }

    /**
     * 单次冒泡排序返回最大
     *
     * @param arr
     */
    private int oneSortAndReturnMax(int[] arr) {
        int i=0;
        for (int j = i+1; j < arr.length; j++) {
            if(arr[i] < arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        return arr[0];
    }

    private void sort(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if(arr[i] < arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{
            {1,2,4},
            {3,3,1}
        };
        new Solution2500().deleteGreatestValue(grid);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
